1. Field of the Invention
This invention relates generally to the field of computer graphics and, more particularly, to graphics systems that render images based on three-dimensional graphics data.
2. Description of the Related Art
A computer system typically relies upon its graphics system for producing visual output on a computer screen or display device. Early graphics systems were only responsible for taking what the processor produced as output and displaying it on the screen. In essence, they acted as simple translators or interfaces. Modem graphics systems, however, incorporate graphics processors with a great deal of processing power. These new graphics systems act more like coprocessors rather than simple translators. This change is due to the recent increase in both the complexity and the amount of data being sent to the display device. For example, modern computer displays have many more pixels, greater color depth, and are able to display images with higher refresh rates than earlier models. Similarly, the images displayed are now more complex and may involve advanced rendering techniques such as anti-aliasing and texture mapping.
As a result, without considerable processing power in the graphics system, the computer system""s CPU would spend a great deal of time performing graphics calculations. This could rob the computer system of the processing power needed for performing other tasks associated with program execution, and thereby dramatically reduce overall system performance. With a powerful graphics system, however, when an application draws a box on the screen, the CPU is freed from having to compute the position and color of each pixel. Instead, the CPU may send a request to the video card stating xe2x80x9cdraw a box at these coordinates.xe2x80x9d The graphics system then draws the box, thereby freeing the CPU to perform other tasks.
Since graphics systems typically perform only a limited set of functions, they may be customized and therefore may be far more efficient at graphics operations than the computer""s general-purpose microprocessor. While early graphics systems were limited to performing two-dimensional (2D) graphics, their functionality has increased to support three-dimensional (3D) wire-frame graphics, 3D solids, and now may include support for textures and special effects such as programmable shading, fogging, alpha-blending, and specular highlighting.
The rendering ability of 3D graphics systems has been improving at a breakneck pace. A few years ago, shaded images of simple objects could only be rendered at a few frames per second, but today""s systems support the rendering of complex objects at 60 Hz or higher. At this rate of increase, in the not too distant future graphics systems will literally be able to render more pixels in realtime than a single human""s visual system can perceive. While this extra performance may be useable in multiple-display environments, it may be wasted in the more common single-display environments. Thus, a graphics system is desired which is capable of utilizing the increased graphics processing power to generate more visually appealing images.
While the number of pixels and frame rate is important in determining graphics system performance, another factor of equal or greater importance is the visual quality of the image generated. One factor that can dramatically improve the perceived quality of an image is the real-time application of certain graphics effects. For example, the ability to anti-alias an image in real-time may dramatically increase the perceived quality of images rendered by a graphics system. Anti-aliasing is a technique for diminishing jagged edges in an image that should be smooth. The jagged edges (sometimes called xe2x80x9cstair-stepsxe2x80x9d or xe2x80x9cjaggiesxe2x80x9d) typically occur because the display device does not have a high enough resolution to represent the edge in a smooth manner. Anti-aliasing reduces the prominence of the jagged edges by surrounding the stair-steps with intermediate shades of color.
Another type of graphics effect that has seen a recent increase in popularity is morphing. The term xe2x80x9cmorphingxe2x80x9d is derived from the word xe2x80x9cmetamorphosisxe2x80x9d and refers generally to an animation technique in which an image of a first object is gradually transformed into an image of a second object. A number of different morphing techniques have been in use for morphing two-dimensional (2D) images (sometimes referred to as xe2x80x9cimage morphingxe2x80x9d). In image morphing, a sequence of images is created that depicts a gradual transition between two images. While these techniques are now well known in image manipulation software, these 2D techniques suffer from a number of drawbacks. These drawbacks include the inability to correctly handle changes in illumination (e.g., shadows) and the inability to properly incorporate features of an object that are not visible in the original 2D image. For example, when a roaring lion opens its mouth during the morph, pulling its lips apart may thicken the lips instead of moving the lips to reveal the lion""s teeth.
Fortunately, there is an alternative to image morphing called xe2x80x9c3D morphingxe2x80x9d or xe2x80x9cvolume morphingxe2x80x9d. This technique is useful for images generated from 3D models as opposed to 2D images. In 3D morphing, a number of intermediate 3D models (called xe2x80x9cmorphsxe2x80x9d) are created directly from the given starting and ending models. Thus, instead of forming intermediate images by interpolating between two 2D images, 3D morphing creates intermediate models (i.e., xe2x80x9cmorphsxe2x80x9d) that are rendered. These morphs may then be rendered using traditional rendering techniques to produce an image sequence depicting the transformation. Since 3D morphing is based on 3D models instead of 2D images, it overcomes the aforementioned shortcomings of image morphing.
Unfortunately, 3D morphing has its own set of drawbacks that may reduce its utility, particularly in real-time 3D computer graphics systems. One major drawback is data bandwidth. To generate realistic or visually appealing scenes, elaborate 3D models are typically employed. For example, a realistic 3D model of a single car may include more than 20,000 graphics primitives (e.g., polygons). Each primitive may have elaborate color, texture map, transparency, and other information associated with it. Thus the bandwidth requirements for transmitting, processing, and rendering the 3D models in real time may be prohibitive.
These obstacles have prevented graphics systems from providing effective support for 3D morphing in a real-time manner (in contrast with offline software solutions). Real-time morphing is desirable because in many applications (e.g., 3D computer games), the viewpoint or camera location may not be known when the game is being compiled. Furthermore, the viewpoint or camera location may change in a dynamic fashion during the morphing sequence. Without the ability to do real-time morphing, the game may be forced to xe2x80x9clock-inxe2x80x9d the viewpoint during the morphing sequence, which could adversely affect the game""s look-and-feel or xe2x80x9cplayabilityxe2x80x9d. Predetermining the viewpoint also limits the applicability of morphing in other real-time applications such as virtual reality environments.
For at least these reasons, a graphics system capable of performing morphing on 3D graphics data is desired. In addition, a graphics system capable of performing morphing in a real-time fashion is desired. Furthermore, a method for encoding 3D graphics data to allow morphing is also desired.
The present invention contemplates the use of 3D geometry compression in connection with embedded weighting information to allow 3D morphing. In some embodiments, the 3D morphing may be implemented as part of the decompression process. In some embodiments, this configuration may have the potential to allow 3D morphing in real-time.
Definitions
As used in this application, the following terms should be broadly construed according to the following definitions:
xe2x80x9cReal-timexe2x80x9d means without a delay that dramatically and adversely impacts the user experience of an interactive application (such as a 3D game). For example, processes performed on a per-frame basis that match a display device""s refresh cycle are considered to be real-time. Furthermore, processes that have small latencies that are not particularly noticeable by the average application users are also considered to be real-time. In contrast, xe2x80x9coff-linexe2x80x9d processes are those that are performed before application execution. An example would be a batch process for rendering frames of 3D movie, wherein each frame requires an hour of processing time to render.
A xe2x80x9cframexe2x80x9d means a single image, e.g., one image of sequence of images that forms a movie or video clip. A frame may be displayed on a display device for one or more refresh cycles. A frame may also be used to refer to the information used to refresh the image on a display device.
A xe2x80x9cgeometric primitivexe2x80x9d is a type of three-dimensional graphics data and is typically viewed as a basic unit or building block that, when used in combination, can form graphical objects. Examples of geometric primitives include: points (dots), lines, vectors, vertices, triangles, polygons, Non-Uniform Rational B-Splines (NURBs), sub-division surfaces, fractals, parametric surfaces, control surfaces, and volume primitives, splines, and particle systems.
A xe2x80x9cgraphical objectxe2x80x9d (or xe2x80x9cobjectxe2x80x9d) is a grouping of three-dimensional graphics data. Typically, but not always, the grouping reflects either an entire real world object or three-dimensional shape, or a portion thereof (e.g., a car may be an object, a car wheel may be an object, or a toroid that forms a car tire may be an object). However, an object may also be a single geometric primitive or a set of randomly assembled geometric primitives.
xe2x80x9cThree-dimensional graphics dataxe2x80x9d (or xe2x80x9c3D graphics dataxe2x80x9d) is a broad term that means data that is used to approximate or represent three-dimensional objects or information in a three-dimensional manner. For example 3D graphics data may include points (dots), lines, vectors, vertices, triangles, polygons, Non-Uniform Rational B-Splines (NURBs), sub-division surfaces, control surfaces, volume elements, normals, geometric primitives, texture mapping information, surface characteristics (e.g., bump mapping information), transparency information, reflectivity information, position and orientation information, environmental information (e.g., fogging), color information, and lighting information.
An xe2x80x9cinitial statexe2x80x9d, as used herein, refers to a first or starting set of information for a graphical object being morphed. For example, the initial state may include one or more of the following types of information: a particular position, orientation, scale, color, shape, size, level of detail, transparency, texture, surface characteristic, environmental information, lighting information, sets of geometric primitives, and other three-dimensional graphics data.
An xe2x80x9cintermediate statexe2x80x9d refers to one or more sets of information that are usable to guide the morphing process from the initial state to the final state. For example, an intermediate state may provide shape information about the graphical object being morphed that corresponds to the shape of the object when it is halfway through the morphing sequence.
A xe2x80x9cfinal statexe2x80x9d, as used herein, refers to a xe2x80x9cdestinationxe2x80x9d set of information that substantially defines (either alone or in combination with other information, e.g., in combination with previous states) the final shape, position, etc., of the graphical object being morphed with respect to the morphing process.
A xe2x80x9cstreamxe2x80x9d of data refers to a sequence of 3D graphics data that may include data for one or more states of one or more graphical objects. A xe2x80x9csub-streamxe2x80x9d of data refers to a subset of the 3D graphics data in a steam, wherein the subset corresponds to a single state.
A xe2x80x9cweighting factorxe2x80x9d refers to information that is usable to determine how much a particular set of graphics data corresponding to a particular state of a graphical object should contribute to a particular frame of morphed output.